package com.lz.tree;

import com.lz.tree.common.TreeNode;

import java.util.*;

/**
 * Tree 先序、中序、后序遍历
 */
public class TreeOrders {


    public static void main(String[] args) {
        TreeOrders treeBianli = new TreeOrders();
        TreeNode treeNode01 = new TreeNode(1);
        TreeNode treeNode02 = new TreeNode(2);
        TreeNode treeNode03 = new TreeNode(3);

        treeNode01.right = treeNode02;
        treeNode02.left = treeNode03;

        treeBianli.DFSInorder(treeNode01);
    }


    /********************BFS 递归遍历******************/

    /**
     * BFS的递归实现
     *
     * @param root
     * @return
     */
    public List<List<TreeNode>> BFSPreorderR(TreeNode root) {
        if (root == null) {
            return null;
        }
        List<List<TreeNode>> list = new ArrayList<>();
        // FIXME: 2020-02-25 技巧,将每一层保存为一个 数组
        doBFS(root, 0, list);
        return list;
    }

    private void doBFS(TreeNode root, int level, List<List<TreeNode>> list) {
        if (root == null) {
            return;
        }
        if (level >= list.size()) {
            List<TreeNode> subList = new ArrayList<>();
            subList.add(root);
            list.add(subList);
        } else {
            list.get(level).add(root);
        }
        doBFS(root.left, level + 1, list);
        doBFS(root.right, level + 1, list);
    }

    /********************DFS 递归遍历******************/

    /**
     * DFS遍历树，递归
     *
     * @param treeNode
     */
    List<Integer> res0 = new ArrayList<>();

    void DFSPreorderR(TreeNode treeNode) {
        if (treeNode == null) return;
        res0.add(treeNode.val);
        DFSPreorderR(treeNode.left);
        DFSPreorderR(treeNode.right);

    }

    /********************BFS 迭代遍历******************/

    /**
     * BFS遍历树，迭代
     *
     * @param treeNode
     */
    void BFSPreorder(TreeNode treeNode) {
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> list = new ArrayList<>();
        TreeNode cur = treeNode;
        queue.add(cur);
        while (queue.size() > 0) {
            TreeNode poll = queue.poll();
            list.add(poll.val);
            if (poll.left != null) queue.add(poll.left);
            if (poll.right != null) queue.add(poll.right);

        }
    }

    /********************DFS 迭代遍历******************/

    /**
     * DFS先序
     */
    List DFSPreorder(TreeNode root) {
        if (root == null) return new ArrayList(1);
        Stack<TreeNode> stack = new Stack();

        List list = new ArrayList<Integer>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {

            while (node != null) {
                stack.add(node.right);
                // FIXME: 2020-02-25 注意{@see Stack}可以添加null元素
                list.add(node.val);
                // stack.add(node);
                node = node.left;
            }
            node = stack.pop();
        }
        System.out.println(list);
        return list;

    }

    /**
     * DFS先序 2
     *
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal01(TreeNode root) {

        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }
        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pollLast();
            output.add(node.val);
            if (node.right != null) {
                stack.add(node.right);
            }
            if (node.left != null) {
                stack.add(node.left);
            }
        }
        return output;

    }

    /**
     * DFS中序
     *
     * @param root
     * @return
     */
    public List<Integer> DFSInorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }


    /**
     * DFS后序
     *
     * @param root
     * @return
     */
    public List<Integer> DFSPostOrder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr.left);
                res.add(curr.val);
                curr = curr.right;
            }
            curr = stack.pop();
        }
        // 翻转
        Collections.reverse(res);
        return res;
    }


}
